//已知前序遍历和中序遍历构造二叉树

class Solution {
    public int i=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
             return    buildTreeChild(preorder,inorder,0,inorder.length-1);
 }
      public TreeNode  buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){


          if(inbegin>inend){
              return null;
          }
          TreeNode root=new TreeNode(preorder[i]);


          //找到当前根在中序遍历的位置
          int rootIndex=  findIndex(inorder,inbegin,inend,preorder[i]);
          i++;
       root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
       root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);
       return root;
      }
      private int findIndex(int[] inorder,int inbegin, int inend,int key){
          for(int i=inbegin;i<=inend;i++){
              if(inorder[i]==key){
                  return i;
              }
          }
          return -1;

      }
}